// 图像渲染： https://leetcode-cn.com/problems/flood-fill/
package main

import "container/list"


// 广度优先遍历，使用used数组避免重复
func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	d := list.New()
	// 定义动作
	dir := [4][2]int{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
	// 定义避免重复计算的map: 主要是 修改值和原值一样的情况，死循环替换。计算过的，就不再计算了
	used := make(map[[2]int]bool, 0)
	root := [2]int{sr, sc}
	used[root] = true
	rootValue := image[sr][sc]
	d.PushBack(root)
	for d.Len() > 0 {
		// 获取当前节点
		node := d.Remove(d.Front()).([2]int)
		image[node[0]][node[1]] = newColor
		// 找到上下左右相邻四节点
		for _, ac := range dir {
			row := node[0] + ac[0]
			col := node[1] + ac[1]
			// 验证是否越界
			if row >= 0 && row < len(image) &&
				col >= 0 && col < len(image[0]) &&
				image[row][col] == rootValue &&
				used[[2]int{row, col}] == false {
				position := [2]int{row, col}
				used[position] = true
				d.PushBack(position)
			}
		}
	}
	// 值传递，直接修改后返回，不影响原来的值
	return image
}


// 官网的 bfs： 遍历时很特别，利用了特性！
var (
	dx = []int{1, 0, 0, -1}
	dy = []int{0, 1, -1, 0}
)

func floodFill1(image [][]int, sr int, sc int, newColor int) [][]int {
	currColor := image[sr][sc]
	if currColor == newColor {
		return image
	}
	n, m := len(image), len(image[0])
	queue := [][]int{}
	queue = append(queue, []int{sr, sc})
	image[sr][sc] = newColor
	for i := 0; i < len(queue); i++ {  // 每次都执行 i < len(queue)，也就是说，每次都会重新计算 len(queue), 下面代码中又会有加入的操作。
		cell := queue[i]
		for j := 0; j < 4; j++ {
			mx, my := cell[0] + dx[j], cell[1] + dy[j]
			if mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor {
				queue = append(queue, []int{mx, my})
				image[mx][my] = newColor
			}
		}
	}
	return image
}


// 深度优先遍历： 官网解法
var (
	dx = []int{1, 0, 0, -1}
	dy = []int{0, 1, -1, 0}
)

func floodFill2(image [][]int, sr int, sc int, newColor int) [][]int {
	currColor := image[sr][sc]
	if currColor != newColor {
		dfs(image, sr, sc, currColor, newColor)
	}
	return image
}

func dfs(image [][]int, x, y, color, newColor int) {
	if image[x][y] == color {
		image[x][y] = newColor
		for i := 0; i < 4; i++ {
			mx, my := x + dx[i], y + dy[i]
			if mx >= 0 && mx < len(image) && my >= 0 && my < len(image[0]) {
				dfs(image, mx, my, color, newColor)
			}
		}
	}
}


